/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-10
 * Time: 22:22
 */


public class Solution {


    /**
     *  方法一: 贪心算法
     */
    public boolean isSubsequence1(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            // 不管是否匹配上, j 一直是要往后移动的
            j++;
        }
        return i == n;
    }


    /**
     *  方法二: DP
     *  dp[i][j] 表示 t 前 i 个字符中是否包含了 s 的前 j 个字符
     *  dp[i][j] = dp[i-1][j] || ((t[i]==s[j]) && dp[i-1][j-1]);
     */
    public boolean isSubsequence2(String s, String t) {
        int row = t.length();
        int col = s.length();
        if (col == 0) {
            return true;
        }
        if (row == 0) {
            return false;
        }
        boolean[][] dp = new boolean[row][col];
        if (t.charAt(0) == s.charAt(0)) {
            dp[0][0] = true;
        }
        for (int i = 1;i < row;i++) {
            dp[i][0] = dp[i-1][0] || (t.charAt(i) == s.charAt(0));
        }
        for (int i = 1;i < row;i++) {
            for (int j = 0;(j < col) && (i >= j);j++) {
                dp[i][j] = (dp[i-1][j] || ((t.charAt(i) == s.charAt(j)) && (j == 0 || dp[i-1][j-1])));
            }
        }
        return dp[row-1][col-1];
    }


    /**
     *  方法三: 通用 DP, 不管你给的 s 是什么,都能快速判断结果
     *  dp[i][j]  表示 t 从 i 下标开始, 之后在什么位置第一次出现 j 字符
     *  转移方程从后往前,
     *  t[i] == j : dp[i][j] = i
     *  t[i] != j : dp[i][j] = dp[i+1][j]
     */
    public boolean isSubsequence3(String s, String t) {
        int n = s.length(), m = t.length();
        // 每行 26 字符
        int[][] f = new int[m + 1][26];
        // 从 lenT 下标开始, dp[i][j] == m 表示 i 之后没有这个字符
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
        }
        // 转移方程
        // dp[i][j]  表示 t 从 i 下标开始, 之后在什么位置第一次出现 j 字符
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        // 开始判断字符串 s
        int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s.charAt(i) - 'a'] == m) {
                return false;
            }
            // 包含当前字符后, 继续往下匹配下一个字符, 起始位置就是当前匹配上的字符的下一个位置
            add = f[add][s.charAt(i) - 'a'] + 1;
        }
        return true;
    }
}
